# 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 
# 
#  说明： 
# 
#  你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 
# 
#  示例 1: 
# 
#  输入: [2,2,1]
# 输出: 1
#  
# 
#  示例 2: 
# 
#  输入: [4,1,2,1,2]
# 输出: 4 
#  Related Topics 位运算 哈希表 
#  👍 1823 👎 0
from functools import reduce
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        d = {}
        for num in nums:
            if num in d:
                d[num] = d[num] + 1
            else:
                d[num] = 1
        for k, v in d.items():
            if v == 1:
                return k
        return 0


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


#  字典存次数, 遍历字典
# def singleNumber(self, nums: List[int]) -> int:
#     # num : 次数
#     d = {}
#     for num in nums:
#         if num in d:
#             d[num] = d[num] + 1
#         else:
#             d[num] = 1
#     for k, v in d.items():
#         if v == 1:
#             return k
#     return 0

"""

异或: 1. 与0异或是自身 2: 与自身异或是0, 3:满足交换律和结合律
2m+1 个数, m个数出现了两次, 1个数出险了一次
故全部异或, 先异或成双的数, 最后异或单独的数, 结果为单独的数

"""
# def singleNumber(self, nums: List[int]) -> int:
#     return reduce(lambda x, y: x ^ y, nums)

if __name__ == '__main__':
    s = Solution()
    n1 = [2, 2, 1]
    assert s.singleNumber(n1) == 1, s.singleNumber(n1)
    n2 = [4, 1, 2, 1, 2]
    assert s.singleNumber(n2) == 4, s.singleNumber(n2)
